package primary.primary0;

import java.util.HashSet;
import java.util.Set;

public class S0142环形链表II {

    /**
     * 答案里的，和2一样，但是直接从head开始，不用判断.next.next，好看一些
     */
    public ListNode detectCycle3(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }

    /**
     * 100, 76
     * 看答案的，巧妙的双指针，快慢指针，妙哇
     * fase走的速度是slow的2倍。相遇的时候，(1) Dfast = 2 Dslow
     * 但是Dfase会比Dslow多转几圈(注意并不是1圈，可能fast指针先入环转了好多圈，slow才进来)
     * 因此(2) Dfast = Dslow + n * b，b为环长度，a为非环的部分的长度
     * 由(1)， (2) 可知，Dslow = n * b，
     * 如何找到环的入口，要从一开始走a + m * b步才行
     * 因此slow再走a步就能找到入口，怎么再走a步?再找一个指针aim，从head走，和slow一样一次一步，当指针aim走了a步之后，slow肯定也在入口处，因此他俩会相等
     */
    public ListNode detectCycle2(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fast = head.next;
        ListNode slow = head;

        while(fast != slow){
            if(fast == null || fast.next == null || fast.next.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        slow = slow.next;
        ListNode aim = head;
        while(aim != slow){
            aim = aim.next;
            slow = slow.next;
        }
        return aim;
    }


    /**
     * 17， 5.4
     * 特殊情况 head == null 还是需要考虑
     * 总之就是逐个找，如果next存在过，那么就返回这个next，注意是要返回next而不是当前节点。
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        Set<ListNode> previousNodes = new HashSet<>();
        ListNode curNode = head;
        previousNodes.add(curNode);
        while(curNode.next != null){
            if(previousNodes.contains(curNode.next)){
                return curNode.next;
            }
            curNode = curNode.next;
            previousNodes.add(curNode);
        }
        return null;
    }

    private class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
